// https://leetcode.cn/problems/path-with-maximum-gold/

// 题干：你要开发一座金矿，地质勘测学家已经探明了这座金矿中的资源分布，
//      并用大小为 m * n 的网格 grid 进行了标注。每个单元格中的整数就表示这一单元格中的黄金数量；如果该单元格是空的，那么就是 0。
//      为了使收益最大化，矿工需要按以下规则来开采黄金：
//      每当矿工进入一个单元，就会收集该单元格中的所有黄金。
//      矿工每次可以从当前位置向上下左右四个方向走。
//      每个单元格只能被开采（进入）一次。
//      不得开采（进入）黄金数目为 0 的单元格。
//      矿工可以从网格中 任意一个 有黄金的单元格出发或者是停止。

// 示例：输入：grid = [[0,6,0],[5,8,7],[0,9,0]]
//       输出：24

// 碎语：同样类型的迷宫问题，注意不要重复，什么点不能进入即可
//       注意x是纵轴，y是横轴

#include <bits/stdc++.h>
using namespace std;

class Solution
{
    bool vis[16][16];
    int m, n;
    int ret;
public:
    int getMaximumGold(vector<vector<int>>& grid)
    {
        // 条件初始化
        m = grid.size(), n = grid[0].size(), ret = 0;
        memset(vis, 0, sizeof(vis));

        // 遍历每一个可能的单元格
        for (int i = 0 ; i < m ; i++){
            for (int j = 0 ; j < n ; j++){
                if (grid[i][j]){ // 该单元格不为0
                    vis[i][j] = true;
                    dfs(grid, i, j, grid[i][j]);
                    vis[i][j] = false;
                }
            }
        }

        return ret;
    }

    int dx[4] = {0,0,-1,1};
    int dy[4] = {-1,1,0,0}; // 上下左右的顺序

    void dfs(vector<vector<int>>& grid, int i, int j, int sum)
    {
        for (int k = 0 ; k < 4 ; k++){
            int x = i + dx[k], y = j + dy[k]; // 新坐标

            if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] && !vis[x][y]){
                vis[x][y] = true;
                dfs(grid, x, y, sum + grid[x][y]);
                vis[x][y] = false;
            }
        }
        ret = max(ret, sum);
    }
};

int main()
{
    Solution sol;
    vector<vector<int>> grid = {{0,6,0},{5,8,7},{0,9,0}};

    cout << sol.getMaximumGold(grid) << endl;

    return 0;
}
